/**
 * 递归求斐波拉契数，代码少容易理解，但运行慢耗内存
 * 但es6有尾调用优化能大部分解决消耗问题，可以经常使用递归解决问题
 */
export function fibonacci(n: number): number {
    if (n < 1) { return 0; } // {1}
    if (n <= 2) { return 1; } // {2}
    return fibonacci(n - 1) + fibonacci(n - 2); // {3}
}
/**
 * 迭代求斐波拉契数，迭代方法会比递归方法快，但代码多
 */
export function fibonacciIterative(n: number) {
    if (n < 1) { return 0; }
    let fibNMinus2 = 0;
    let fibNMinus1 = 1;
    let fibN = n;
    for (let i = 2; i <= n; i++) {
        // n >= 2
        fibN = fibNMinus1 + fibNMinus2; // f(n-1) + f(n-2)
        fibNMinus2 = fibNMinus1;
        fibNMinus1 = fibN;
    }
    return fibN;
}
/**
 * 迭代求斐波拉契数（记忆化，用数组缓存结果），运行较快（但还是比迭代慢）
 */
export function fibonacciMemoization(n: number) {
    if (n < 1) { return 0; }
    const memo = [0, 1];
    const fibonacciMem = (num: number): number => {
        if (memo[num] != null) { return memo[num]; }
        return (memo[num] = fibonacciMem(num - 1) + fibonacciMem(num - 2));
    };
    return fibonacciMem(n);
}
